'''
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
内存限制64M
'''

#1 超时
class Solution:
    def jumpFloor(self, n):
        # write code here
         if n<=1: return 1
         return self.jumpFloor(n-1) + self.jumpFloor(n-2)
#2 堆栈溢出 记忆遍历过的节点
# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, n):
        # write code here
        dp={}
        if n<=1:
            return 1
        if dp[n]:
            return dp[n]
        dp[n] = self.jumpFloor(n-1) + self.jumpFloor(n-2)
        return dp[n]
#3 动态规划
class Solution:
    def jumpFloor(self, n):
        # write code here
        if n==1:
            return 1
        res = [0,1,2]
        # 等于n还是要进因为之前0也算了一位
        while len(res)<=n:
            res.append(res[-1]+res[-2])
        return res[-1]
#4 继续优化空间
# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, n):
        # write code here
        if n== 1:
            return 1
        elif n == 2:
            return 2
        elif n == 0:
            return 1
        prev1 = 2
        prev2 = 1
        for i in range(3,n+1):
            res = prev1 + prev2
            prev2 = prev1
            prev1 = res
        return res